package com.future;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Description: BM92 最长无重复子数组
 *
 * @author weiruibai.vendor
 * Date: 2022/7/28 14:12
 */
public class Solution_BM92 {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 3, 2, 1, 3, 3, 3, 1};
        System.out.println(maxLength(arr));
    }

    public static int maxLength(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return 1;
        }
        int ans = 0;
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (Integer num : arr) {
            if (linkedList.contains(num)) {
                ans = Math.max(ans, linkedList.size());
                while (linkedList.contains(num)) {// ！！！！
                    linkedList.pollLast();
                }
            }
            linkedList.addFirst(num);
        }
        ans = Math.max(ans, linkedList.size());
        return ans;
    }

    public static int maxLength_v2(int[] arr) {
        //用链表实现队列，队列是先进先出的
        Queue<Integer> queue = new LinkedList<>();
        int res = 0;
        for (int c : arr) {
            while (queue.contains(c)) {
                //如果有重复的，队头出队
                queue.poll();
            }
            //添加到队尾
            queue.add(c);
            res = Math.max(res, queue.size());
        }
        return res;
    }
}
